<HTML>
<HEAD>
<TITLE>CS 440 Program 5</TITLE>
</HEAD>
<font size = 4>
<body bgcolor = "ffffff">

<CENTER><H2>CS 440
<BR>Program 5</H2></CENTER>
<H3><CENTER>due December 2, 2011
</CENTER></H3>

<H3>The Program</H3>

In this program you will finish your PAXI compiler by implementing
subprograms (procedures).  This will involve generating code from
productions 10 (&lt;procedure_decl&gt;), 25 (&lt;call&gt;), 26
(&lt;return_value&gt;), 29 &lt;quantity&gt; (third right-hand side),
adding some code to the first right-hand side of production 30
(&lt;variable&gt;), and minor additions to a few other productions to
accomodate local variables and parameters.

<H3>The Stack Frame</H3>

When a procedure is called a block of locations on the stack is
allocated for the use of the procedure.  This area is called a
<EM>stack frame</EM> and it contains the return address, parameters
passed to the procedure, local variables, and any values which must be
preserved over the procedure call.

<P>Reading parameters and local variables from within a procedure
requires being able to read the stack frame.  This requires the use of
a new register, the <EM>frame pointer</EM>.  You will use <EM>Register
1</EM> for this (recall that Register 0 is the stack pointer).  The
purpose of the frame pointer is to hold the address of a position in
the stack frame so parameters and local variables can easily be
addressed.  The frame pointer will hold its value throughout the
activation of a procedure whereas the stack pointer will be changing
its value frequently, making it inappropriate for finding addresses
within the stack frame.  Code will be generated from production 10
(&lt;procedure_decl&gt;) to set up the frame pointer: first the
current value of the frame pointer will be pushed onto the stack, and
then the value of the stack pointer will be copied to the frame
pointer.

<P>The stack frame is set up on procedure entry which works as
follows.  The parameters were pushed onto the stack <EM>before</EM>
the procedure was called and the return address was pushed onto the
stack by the <EM>call</EM> instruction.  Within the procedure (from
production 10) the frame pointer is then set up as described above.
Space for local variables is then allocated (before
&lt;statement_list&gt;) by <EM>decrementing</EM> the stack pointer.

<P>On exit from a procedure the stack frame must be cleared.  Code to
do this is also generated from &lt;procedure_decl&gt; but
<EM>after</EM> &lt;statement_list&gt;.  First the local variables must
be <EM>deallocated</EM> (increment the stack pointer by the number of
local variables), then the frame pointer must be restored (popped into
Register 1).  Finally the parameters are removed from the stack by
using the parameter count as an argument to the <EM>return</EM>
instruction.  At this point your program should determine if the
procedure is <STRONG>main</STRONG>.  If it is main a <EM>stop</EM>
instruction should be generated instead of a return.

<H3>Accessing the Stack Frame</H3>

<IMG src="stk-frm.gif" alt="[Sketch of a stack frame showing positions
of parameters, return address, old frame pointer, local variables, and
use of frame pointer and stack pointer]" align="left"> Parameters are
read and written to relative the frame pointer.  A glance at the
figure at the left shows that the offset from the frame pointer of the
nth parameter is (p - n + 2) where p is the number of parameters on
the stack.  This is a constant which can be computed at compile time
(i.e. computed in the compiler, not in code generated <EM>by</EM> the
compiler).  Code is generated which adds this constant to the frame
pointer to get the address of the parameter which is then pushed onto
the stack.  All of this is done from (the first right-hand side of)
production 30 (&lt;variable&gt;).  PAXI does not allow arrays as
parameters so no additional action need be taken in the second
right-hand side here.  Doing this requires that the parameter count be
available to the &lt;variable&gt; production.  Recall that this value
was stored in a global variable in your bison file in Program 3.

<P>No work is need to <EM>pass parameters</EM> to a procedure since
code already generated from &lt;arithmetic_expression&gt; leaves the
values (in the correct order) on the stack.

<P>In order for local variables to be accessible, code must be
generated from &lt;variable&gt; to leave the address of a local
variable on the stack.  Again, since PAXI doesn't allow arrays as
local variables you only need worry about this in the first right-hand
side of the production.  Finding addresses of local variables is done
by generating code which computes the location of the local variable
relative to the frame pointer.  This is similar to (but easier than)
finding the location of a parameter.  Consult the figure above to see
how this might be done.

<H3>Procedure Calls</H3>

Procedure calls are made from production 25, &lt;call&gt;.  The number
of actual parameters will be counted in productions 28,
&lt;parameter_list&gt;, and 27, &lt;actual_parameters&gt;.  In
&lt;call&gt; this count will be compared with the number of parameters
expected (look up the symbol table entry for the procedure).  A
<EM>call</EM> instruction will be generated using the location field
of the symbol table entry as its argument.

<H3>Return Values</H3>

PAXI procedures may return values.  This is done with the
<EM>retval</EM> statement described in production 26.  Code generated
here will pop the top-of-stack value (from
&lt;arithmetic_expression&gt;) into <EM>Register 2</EM> which is
reserved for this purpose.  In the third right-hand side of production
29 (&lt;quantity&gt;) this value will be pushed onto the stack.  Thus
the value from the <EM>last</EM> retval statement executed in a
procedure will become the returned value.

<H3>Etc.</H3>

When you make the symbol table entry for a procedure you can now write
its entry point for the location field.  This will be the value of the
counter used for your code generation before any code is generated
from &lt;procedure_decl&gt;.  You must check that the program being
compiled has a <STRONG>main</STRONG> procedure (check the symbol
table) and use its location field as the entry point value when
writing the header.

<P>The only changes to Program 1 are that the entry point from the
PVM file header will be used to initialize IP. This will start
execution from <STRONG>main</STRONG> rather than from the beginning of
the program, and the frame pointer, Register 1, will be initialized to
the same initial value as the stack pointer, Register 0.

<H3>To Hand In</H3>

You will hand in source code and a sample terminal session.  The only
source code you need to hand in is your bison file.  

</HTML>
